package Hot100.Medium.Sort;

import java.util.Arrays;
import java.util.Random;

public class QuickSort {
    public static int[] quickSort(int[] arr) {
        if (arr == null || arr.length == 1) return new int[0];
        sort(arr, 0, arr.length - 1);
        return arr;
    }

    private static void sort(int[] arr, int left, int right) {
        // 递归结束的条件
        if (left >= right) return;

        int pivot = arr[(left + right) / 2];  // 选择中间元素作为基准
        int i = left, j = right;

        // 分区操作
        while (i <= j) {
            while (arr[i] < pivot) i++;  // 从左找第一个 >= pivot 的
            while (arr[j] > pivot) j--;  // 从右找第一个 <= pivot 的

            if (i <= j) {
                // 交换元素
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
                j--;
            }
        }
        // 递归排序左右子数组
        sort(arr, left, j);
        sort(arr, i, right);
    }

    // 测试
    public static void main(String[] args) {
        int[] arr = {6, 3, 8, 2, 9, 1, 5, 7, 4};
        quickSort(arr);
        System.out.println(java.util.Arrays.toString(arr));
        // 输出: [1, 2, 3, 4, 5, 6, 7, 8, 9]
    }
}